package main

import (
	"fmt"
	"sort"
)

func main() {
	fmt.Println(len(subs("aabbc")))
	fmt.Println(len(permutation("aabbc")))
}

func subs(input string) []string {
	bytes := []byte(input)
	var paths []string
	fastSort(bytes)
	fmt.Println(bytes)
	var subsHelper func([]byte, []byte)
	subsHelper = func(input []byte, path []byte) {
		if len(input) == 0 {
			paths = append(paths, string(path))
		}
		for i := 0; i < len(input); i++ {
			if i > 0 && input[i] == input[i-1] {
				continue
			}
			input[0], input[i] = input[i], input[0]
			path = append(path, input[0])
			subsHelper(input[1:], path)
			input[0], input[i] = input[i], input[0]
			path = path[:len(path)-1]
		}
	}
	subsHelper(bytes, []byte{})
	return paths
}

func fastSort(input []byte) {
	if len(input) <= 1 {
		return
	}
	mid := input[0]
	var i, j int
	for i, j = 1, len(input)-1; i < j; {
		for ; i <= j && input[i] <= mid; i++ {
		}
		for ; i <= j && input[j] > mid; j-- {
		}
		if i < j {
			input[i], input[j] = input[j], input[i]
		}
	}
	input[j], input[0] = input[0], input[j]
	fastSort(input[:j])
	fastSort(input[i:])
}

func permutation(s string) (ans []string) {
	t := []byte(s)
	sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
	length := len(t)
	var path []byte
	var vis = make([]bool, length)
	var backtrack func(int)
	backtrack = func(i int) {
		if i == length {
			ans = append(ans, string(path))
		}
		for j, v := range vis {
			if v || j > 0 && !vis[j-1] && t[j-1] == t[j] {
				continue
			}
			path = append(path, t[j])
			vis[j] = true
			backtrack(i + 1)
			vis[j] = false
			path = path[:i]
		}
	}
	backtrack(0)
	return
}
